/**
 * 357. 计算各个位数不同的数字个数
 * https://leetcode-cn.com/problems/count-numbers-with-unique-digits/
 */
public class Solutions_357 {
    public static void main(String[] args) {
//        int n = 0;  // output: 1
//        int n = 1;  // output: 10
//        int n = 2;  // output: 91
        int n = 3;  // output: 739
//        int n = 4;  // output: 5275
//        int n = 5;  // output: 32491
//        int n = 6;  // output: 168571
//        int n = 7;  // output: 712891
//        int n = 8;  // output: 2345851
//        int n = 9;  // output: 5611771
//        int n = 10;  // output: 8877691

        int result = countNumbersWithUniqueDigits(n);
        System.out.println(result);
    }

    /**
     * 解题思路：排列组合
     * 第 1 位：除 0 不可选，可选 [1, 9]，共有 9 种可能
     * 第 2 位：本可选 [0, 9] 区间的数字，共 10 种可能
     *      但是第 1 位选了一位，不能重复，那么只有 10 - 1 = 9 种可能
     * 第 3 位：本可选 [0, 9] 区间的数字，共 10 种可能
     *      但是第 1, 2 位各选了一位，不能重复，那么只有 10 - 2 = 8 种可能
     * 第 4 位：本可选 [0, 9] 区间的数字，共 10 种可能
     *      但是第 1, 2, 3 位选了一位，不能重复，那么只有 10 - 3 = 7 种可能
     * ...
     *
     * 关键：2 位时不同位的数字个数 = 2 位数时不同位的数字个数 + 1 位数时不同位的数字个数
     */
    public static int countNumbersWithUniqueDigits(int n) {
        // dp[2] = 91，表示 2 位数时，[0, 100) 区间内，所有位不同的数字共有 91 个
        int[] dp = new int[n + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            // 第 1 位时，[0, 9] 的数字中可选 [1, 9]，数字 0 不可以选，那么有 9 种可能
            dp[i] = 9;
            // 再找第 [2, i - 1] 位
            for (int j = 1; j < i; j++) {
                // 计算排列组合：可能次数相乘
                dp[i] *= 10 - j;
            }
            dp[i] += dp[i - 1];
        }
        return dp[n];
    }
}
